package leetcode.dp;

/**
 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

 */
public class NumSquares279 {
    public int numSquares(int n) {
//        dp【i】表示，数字i最少能完全平方的个数
        int []dp = new int[n+1];

        for (int i = 0; i < dp.length; i++)
            dp[i] = Integer.MAX_VALUE-1;

        dp[0]=0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j*j<=i ; j++) {
                dp[i] = Math.min(dp[i-j*j]+1,dp[i]);
            }
        }
        return  dp[n];
    }


}